
public class RedBlack<T extends Comparable<T>> {
	public final static String COLOR_BLACK = "black";
    public final static String COLOR_RED = "red";
    

    
    public Node<T> root;
    public int size;
    
     
    public Node<T> grandparent(Node<T> n){
    	if(n != null && n.parent != null){
    		return n.parent.parent;
    	} else{
    		return null;
    	}
    }
    public Node<T> uncle(Node<T> n){
    	Node<T> g = grandparent(n);
    	if(g == null) return null;
    	if(n.parent == g.left){
    		return g.right;
    	} else{
    		return g.left;
    	}
    }
    
    public String getSide(Node<T> n){
    	Node<T> curr = n;
    	Node<T> after = n.parent;
    	if(after.left == curr) return "LEFT";
    	else return "RIGHT";
    }
    
    public void insert(T data){
    	checkInsertCase(add(data));
    }
    public Node<T> add(T value){
		if(isEmpty()){
			root = new Node<T>(value, null, null, null, COLOR_BLACK,null);
			size ++;
			return root;
		}
		Node<T> temp = root;
		Node<T> insert = new Node<T>(value, null, null, null, COLOR_RED,null);
		while(true){
			if(temp.data.compareTo(value) > 0){
				if(temp.left == null){
					insert.side = "LEFT";
					insert.parent = root;
					temp.left = insert;
					size++;
					return insert;
				} else temp = temp.left;
			} else{
				if(temp.right == null){
					insert.side = "RIGHT";
					insert.parent = root;
					temp.right = insert;
					size++;
					return insert;
				} else temp = temp.right;
				
			}
		}
    }
    public Node<T> checkInsertCase(Node<T> current){
    	while(true){
    		if(current == root){
    			return current;
    		} else if(current.parent.color.equals(COLOR_BLACK)){
    			return current;
    		} else if(uncle(current) == null || uncle(current).color.equals(COLOR_BLACK)){
    			if(current.parent.side.equals("LEFT")){
    				if(current.side.equals("LEFT")){
    					current.parent.color = COLOR_BLACK;
    					grandparent(current).color = COLOR_RED;
    					rotateRight(grandparent(current));
    					return current;
    				} else{
    					grandparent(current).color = COLOR_RED;
    					current.color = COLOR_BLACK;
    					leftRight(current);
    					return current;
    				}
    			} else{
    				if(current.side.equals("RIGHT")){
    					grandparent(current).color = COLOR_RED;
    					current.parent.color = COLOR_BLACK;
    					rotateLeft(grandparent(current));
    					return current;
    				} else{
    					grandparent(current).color = COLOR_RED;
    					current.color = COLOR_BLACK;
    					rightLeft(current);
    					return current;
    				}
    			}
    		} else{
    			current.parent.color= COLOR_BLACK;
    			uncle(current).color = COLOR_BLACK;
    			if(grandparent(current) == root){
    				return current;
    			} else{
    				grandparent(current).color = COLOR_RED;
    				current = grandparent(current);
    			}
    		}
    	}
    }
    
//    public Node<T> rotateRight(Node<T> current) {
//        Node<T> leftChild = current.left;
//        current.left = leftChild.right;
//        
//        if(current.left != null) {
//            current.left.parent = current;
//            //current.left.side = SIDE_LEFT;
//        }
//
//        leftChild.right = current;
//        //leftChild.side = current.side;
//        leftChild.parent = current.parent;
//
//        // Moves up the tree and updates relationships
//        Node<T> parent = current.parent;
//        Node<T> child = leftChild;
//        while (parent != null) {
//            if (getSide(child).equals("LEFT")) {
//                parent.left = child;
//            } else {
//                parent.right = child;
//            }
//            child = parent;
//            parent = parent.parent;
//        }
//        this.root = child;
//
//        current.parent = leftChild;
//        //current.side = SIDE_RIGHT;
//
//        return leftChild;
//    }
//
//    public Node<T> rotateLeft(Node<T> current) {
//        Node<T> rightChild = current.right;
//        current.right = rightChild.left;
//        
//        if(current.right != null) {
//            current.right.parent = current;
//            //current.right.side = SIDE_RIGHT;
//        }
//        
//
//        rightChild.left = current;
//        //rightChild.side = current.side;
//        rightChild.parent = current.parent;
//
//        // Moves up the tree and updates relationships
//        Node<T> parent = current.parent;
//        Node<T> child = rightChild;
//        while (parent != null) {
//            if (getSide(child).equals("LEFT")){
//                parent.left = child;
//            } else {
//                parent.right = child;
//            }
//            child = parent;
//            parent = parent.parent;
//        }
//        this.root = child;
//
//        current.parent = rightChild;
//        //current.side = SIDE_LEFT;
//
//        return rightChild;
//    }
//    
//    public void leftRight(Node<T> b) {
//        Node<T> c = grandparent(b);
//        Node<T> a = b.parent;
//        
//        a.right = b.left;
//        if(a.right != null) {
//            //a.right.side = SIDE_RIGHT;
//            a.right.parent = a;
//        }
//        b.left = a;
//        a.parent = b;
//        //b.side = c.side;
//        
//        b.parent = c.parent;
//        if(b.parent != null) {
//            if(getSide(b).equals("LEFT")) {
//                b.parent.left = b;
//            } else {
//                b.parent.right = b;
//            }
//        }
//        
//        c.left = b.right;
//        if(c.left != null) {
//            //c.left.side = SIDE_LEFT;
//            c.left.parent = c;
//        }
//        b.right = c;
//        c.parent = b;
//        
//        if(c == this.root) {
//            this.root = b;
//        }
//        
//    }
//    
//    public void rightLeft(Node<T> b) {
//        Node<T> c = grandparent(b);
//        Node<T> a = b.parent;
//        
//        a.left = b.right;
//        if(a.left != null) {
//            //a.left.side = SIDE_LEFT;
//            a.left.parent = a;
//        }
//        b.right = a;
//        a.parent = b;
//        //b.side = c.side;
//        
//        b.parent = c.parent;
//        if(b.parent != null) {
//            if(getSide(b).equals("LEFT")) {
//                b.parent.left = b;
//            } else {
//                b.parent.right = b;
//            }
//        }
//        
//        c.right = b.left;
//        if(c.right != null) {
//            //c.right.side = SIDE_RIGHT;
//            c.right.parent = c;
//        }
//        b.left = c;
//        c.parent = b;
//        
//        if(c == this.root) {
//            this.root = b;
//        }
//    }

    public Node<T> rotateRight(Node<T> k1){
    	Node<T> k2 = k1.right;
    	k1.right = k2.left;
    	k2.left=k1;
    	return k2;
    }
    public Node<T> rotateLeft(Node<T> k2){
    	Node<T> k1 = k2.left;
    	k2.left = k1.right;
    	k1.right = k2;
    	return k1;
    }
    public Node<T> rightLeft(Node<T> k1){
    	k1.right = rotateLeft(k1.right);
    	return rotateRight(k1);
    } 
    public Node<T> leftRight(Node<T> k3){
    	k3.left = rotateRight(k3.left);
    	return rotateLeft(k3);
    }
    
    public void inOrder(Node<T> temp){
    	if(temp == null) return;
    	inOrder(temp.left);
    	System.out.println(temp.data + " Color: " + temp.color);
    	inOrder(temp.right);
    }
   

    
//    public void add(T value){
//    	Node<T> addingNode = new Node<T>(value, null, null, null, null);
//    	insertCase1(addingNode);
//    	size++;
//    }
//
//    public void insertCase1(Node<T> n){
//    	if(n.parent == null){
//    		n.color = COLOR_BLACK;
//    	} else{
//    		insertCase2(n);
//    	}
//    }
//    public void insertCase2(Node<T> n){
//    	if(n.parent.color.equals(COLOR_BLACK)){
//    		returnl
//    	}
//    }

//    public Node<T> add(T value){
//		if(isEmpty()){
//			root = new Node<T>(value, null, null, null, COLOR_BLACK);
//			size ++;
//			return root;
//		}
//		Node<T> temp = root;
//		Node<T> insert = new Node<T>(value, null, null, null, COLOR_RED);
//		while(true){
//			if(temp.data.compareTo(value) > 0){
//				if(temp.left == null){
//					insert.parent = root;
//					temp.left = insert;
//					size++;
//					return insert;
//				} else temp = temp.left;
//			} else{
//				if(temp.right == null){
//					insert.parent = root;
//					temp.right = insert;
//					size++;
//					return insert;
//				} else temp = temp.right;
//				
//			}
//		}
//    }
//    
//    public Node<T> remove(T value){}
    
    private boolean isEmpty(){
    	return (root == null);
    }
    public Node<T> getRoot(){
    	return root;
    }
    
    
    
public static void main(String[] args){
    	RedBlack<Integer> testing = new RedBlack<Integer>();
    	testing.insert(17);
    	testing.insert(18);
    	testing.insert(20);
    	testing.insert(21);
    	testing.inOrder(testing.root);
    }
}
